package utility;

public abstract class TreeEntry {
	TreeEntry left=null;
	TreeEntry right=null;
	TreeEntry parent=null;
	Integer	left_count=0;
	Integer	right_count=0;
	Integer	self_count=1;
	
	abstract public boolean IsReady();
	abstract public Integer CompareTo(TreeEntry AnotherTreeEnty);
	
	public TreeEntry(){
		return ;
	}
	
	public boolean InsertLeft(TreeEntry entry){
		if(this.left==null){
			this.left=entry;
			entry.parent=this;
			this.left_count++;
			return true;
		}
		return false;
	}

	public boolean InsertRight(TreeEntry entry){
		if(this.right==null){
			this.right=entry;
			entry.parent=this;
			this.right_count++;
			return true;
		}
		return false;
	}
	
	public TreeEntry InsertAtIncreasedOrder(TreeEntry entry){
		if(!this.IsReady())
			return null;
		
		if(this.CompareTo(entry)>=0){
			if(this.left==null){
				this.left=entry;
				entry.parent=this;
				this.left_count++;
				return this.left;
			}
			TreeEntry ret=this.left.InsertAtIncreasedOrder(entry);
			if(ret!=null){
				this.left_count++;
			}
			return ret;
		}else if(this.CompareTo(entry)<0){
			if(this.right==null){
				this.right=entry;
				entry.parent=this;
				this.right_count++;
				return this.right;
			}
			TreeEntry ret=this.right.InsertAtIncreasedOrder(entry);
			if(ret!=null){
				this.right_count++;
			}
			return ret;
		}
		
		return null;
		
	}
	
	public TreeEntry InsertAtIncreasedOrderExculded(TreeEntry entry){
		if(!this.IsReady())
			return null;
		
		if(this.CompareTo(entry)>0){
			if(this.left==null){
				this.left=entry;
				entry.parent=this;
				this.left_count++;
				return this.left;
			}
			TreeEntry ret=this.left.InsertAtIncreasedOrderExculded(entry);
			if(ret!=null){
				this.left_count++;
			}
			return ret;
			
		}else if(this.CompareTo(entry)<0){
			if(this.right==null){
				this.right=entry;
				entry.parent=this;
				this.right_count++;
				return this.right;
			}
			
			TreeEntry ret=this.right.InsertAtIncreasedOrderExculded(entry);
			if(ret!=null){
				this.right_count++;;
			}
			
			return ret; 
		}
		
		this.self_count++;
		return this;
	}
	
	public TreeEntry FindFloorClose(TreeEntry wei){
		if(!this.IsReady()||wei==null||!wei.IsReady()){
			return null;
		}
		
		if(this.CompareTo(wei)==0){
			return this;
		}else	if(this.CompareTo(wei)>0){
			if(this.left==null){
				return null;
			}
			return this.left.FindFloorClose(wei);
		}else 	if(this.CompareTo(wei)<0){
			if(this.right==null){
				return this;
			}
			TreeEntry tmp=this.right.FindFloorClose(wei);
			return tmp==null?this:tmp;
		}else{
			return null;	/* never come here */
		}
	}
	
	public TreeEntry FindCeilingClose(TreeEntry wei){
		if(!this.IsReady()||wei==null||!wei.IsReady()){
			return null;
		}
		
		if(this.CompareTo(wei)==0){
			return this;
		}else	if(this.CompareTo(wei)<0){
			if(this.right==null){
				return null;
			}
			return this.right.FindCeilingClose(wei);
		}else 	if(this.CompareTo(wei)>0){
			if(this.left==null){
				return this;
			}
			TreeEntry tmp=this.left.FindCeilingClose(wei);
			return tmp==null?this:tmp;
		}else{
			return null;	/* never come here */
		}
	}
	
	public Integer GetLeftCount(){
		return this.left_count;
	}
	
	public Integer GetRightCount(){
		return this.right_count;
	}
	
	public Integer GetSelfCount(){
		return this.self_count;
	}
	
	public Integer GetChildrenCount(){
		return this.left_count+this.right_count;
	}
	
	public Integer GetAllEntryCount(){
		//include self
		return this.GetChildrenCount()+this.GetSelfCount();
	}
	
	public TreeEntry	GetMaxRight(){
		TreeEntry srh=this;
		while(srh.right!=null){
			srh=srh.right;
		}
		return srh;
	}
	
	public TreeEntry	GetMaxLeft(){
		TreeEntry srh=this;
		while(srh.left!=null){
			srh=srh.left;
		}
		return srh;
	}
	
	public TreeEntry GetLeft(){
		return this.left;
	}
	
	public TreeEntry GetRight(){
		return this.right;
	}
	
	public TreeEntry GetParent(){
		return this.parent;
	}
}
